package 蓝桥杯算法;

public class day25 {
    public static void main(String[] args) {
   day25 a=new day25();
   String[] str={"10","0001","111001","1","0"};
   System.out.println( a.find(str,5,3));
   int[] weight={1,3,4};
   int[] value={15,20,30};
        System.out.println(a.bag(weight,value,4));
        int[] arr={1,2,3};
        int amount=5;
        System.out.println(a.change(arr,amount));
        int[] num2={1,2,3};
        System.out.println(a.combinationSum4(num2,4));
        System.out.println(a.climb(2,3));
    }

   public int findTarget(int[] num,int target){
        int sum=0;
        for(int i:num){
            sum+=i;
        }
        if(Math.abs(target)>sum){
            return 0;
        }
        if((target+sum)%2==1){
            return 0;
        }
        int bigweight=(target+sum)/2;
        int[] dp=new int[bigweight+1];
        dp[0]=1;
        for(int i=1;i<num.length;i++){
            for(int j=bigweight;j>=num[i];j--){
                dp[j]+=dp[j-num[i]];
            }
        }
        return dp[bigweight];
   }
   public int find(String[] num,int m,int n){
        int [][]dp=new int[m+1][n+1];
        dp[0][0]=0;
        for(String str: num){
            int x=0,y=0;
            for(char ch:str.toCharArray()){
                if(ch=='1'){
                    x++;
                }
                else{
                    y++;
                }
            }
            for(int i=m;i>=y;i--){
                for(int j=n;j>=x;j--){
                    dp[i][j]=Math.max(dp[i][j],dp[i-y][j-x]+1);
                    //放了新的值，直到找到该位置可以放的最大值
                }
            }


        }
        return dp[m][n];
   }
   public int bag(int[] weight,int[] value,int bagweight){
        int[][] dp=new int[weight.length][bagweight+1];
        dp[0][0]=0;
        for(int j=weight[0];j<=bagweight;j++){
            dp[0][j]=dp[0][j-weight[0]]+value[0];
        }
        for(int i=1;i<weight.length;i++){
            for(int j=0;j<=bagweight;j++){
                if(j<weight[i]){//内存不够
                    dp[i][j]=dp[i-1][j];
                }
                else{
                    //与其上面的比较，或者减去相应的值
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-weight[i]]+value[i]);
                }
            }
        }
        return dp[weight.length-1][bagweight];
   }
   public int coin(int[]coins,int amount){
        if(amount==0){
            return 0;
        }
        int[][]dp=new int[coins.length][amount+1];
        dp[0][0]=0;
       for(int i=0;i<coins.length;i++){
           dp[i][0]=1;
       }
       for(int j=coins[0];j<=amount;j++){
           dp[0][j]+=dp[0][j-coins[0]];
       }
        for(int i=1;i<coins.length;i++){
            for(int j=coins[i];j<=amount;j++){
                if(j<coins[i]){
                    dp[i][j]=dp[i-1][j];
                }
                else{
                   dp[i][j]=dp[i-1][j]+dp[i][j-coins[i]];
                }
            }
        }
        return dp[coins.length-1][amount];
   }
   public int change(int[] coins,int amount){
        int[] dp=new int[amount+1];
        dp[0]=1;
        for(int i=0;i<coins.length;i++){//遍历硬币
            for(int j=coins[i];j<=amount;j++){
                //如果可以放入，把其余可剩余相同的背包的方法个数相加
                dp[j]+=dp[j-coins[i]];

            }
        }
        return dp[amount];
   }
       public int combinationSum4(int[] nums, int target) {
           int[] dp = new int[target + 1];
           dp[0] = 1;
           for (int i = 0; i <= target; i++) {
               for (int j = 0; j < nums.length; j++) {
                   if (i >= nums[j]) {
                       dp[i] += dp[i - nums[j]];
                   }
               }
           }
           return dp[target];
       }
       public int climb(int m,int n){//完全背包问题
        int[] dp=new int[n+1];
        dp[0]=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(i>=j){
                    dp[i]+=dp[i-j];
                }
            }
        }
        return dp[n];
       }
}
